package class06

/*
	给定一个正整数arr，返回该数组能不能分成四个部分，并且每个部分的累加和相等，切分的位置数不要。
	例如：
		arr = [3,2,4,1,4,9,5,10,1,2,2] 返回 true
		三个切割点下标返回2，5，7 切出的四个子数组为[3,2],[1,4],[5],[1,2,2]
		累加和都是5

	解题思路：
		使用一个map记录前缀和
		如： [1,7,6,4,2]
			map{1:0, 8:1, 14:2, 18:3, 20:4}
			枚举第一刀的位置，然后直到前缀和之后，查表获取第二刀的位置，和后续刀的位置。

		第一刀的位置枚举：(N-6),N-5,(N-4),N-3,(N-2),N-1, 最后一刀能到达的最后位置为N-6

		[x i x j x k x]
		i 为 第一刀，算出第一部分的和
		寻找第二刀，第二刀的前缀和必须为 sum = 2*x + i + j
		寻找第三刀，第三刀的前缀和必须为 sum = 3*x + i + j + k
		算出第四部分的和为 x
*/
func CanSplits1(arr []int) bool {
	if len(arr) < 7 {
		return false
	}
	preSumMap := make(map[int]int)
	sum := 0
	for i:=0; i<len(arr); i++ {
		sum += arr[i]
		preSumMap[sum] = i
	}
	preSumArr := make([]int, len(arr))
	preSumArr[0] = arr[0]
	for i:=1; i<len(preSumArr); i++ {
		preSumArr[i] = preSumArr[i-1] + arr[i]
	}

	for i:=1; i<=len(arr)-6; i++ {
		firstSum := preSumArr[i] - arr[i]
		iNum := arr[i]
		// 寻找第二刀
		jNum := 0
		if j, ok := preSumMap[2*firstSum+iNum]; ok && j+1<len(arr) {
			jNum = arr[j+1]
		} else {
			continue
		}
		// 寻找第三刀
		kIndex := 0
		if k, ok := preSumMap[3*firstSum+iNum+jNum]; ok && k+1 < len(arr) {
			kIndex = k+1
		} else {
			continue
		}
		// 计算最后的总和
		lastSum := preSumArr[len(arr)-1] - preSumArr[kIndex]
		if lastSum == firstSum {
			return true
		}
	}
	return false
}
